package java_thinking.unit_21._21_15;


import javax.annotation.concurrent.ThreadSafe;
import java.util.concurrent.atomic.AtomicReference;

/**
 * @Desc:   15.7 非阻塞算法中的插入算法 来自 Michael-Scott [skɑt]
 * @author: cww
 * @DateTime: 2019-06-29 21:50
 */
@ThreadSafe
public class LinkedQueue<E> {
    private static class Node<E> {
        final E item;
        final AtomicReference<Node<E>> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            //但这里使用 AtomicReference 来构建每个 Node 会极大的降低插入操作的开销
            this.next = new AtomicReference<Node<E>>(next);
        }
    }

    /**
     * 哨兵节点
     */
    private final Node<E> dummy = new Node<>(null, null);
    /**
     * 头尾节点指向哨兵节点
     */
    private final AtomicReference<Node<E>> head = new AtomicReference<>(dummy);
    private final AtomicReference<Node<E>> tail = new AtomicReference<>(dummy);

    public boolean put(E item) {
        //将要替换到链尾的 Node
        Node<E> newNode = new Node<>(item,null);
        while (true) {
            //当前的尾部指针
            Node<E> curTail = tail.get();
            //当前尾部的next指针
            Node<E> tailNext = curTail.next.get();
            //这一步如果不等说明另外一个线程已经把尾部替换好了，直接放弃，进入下一次替换
            //注意会发生 ABA 问题
            if (curTail == tail.get()) {
                //处于中间态，先为其他线程执行到的中间态完成他的工作，替换当前尾节点，
                // 这个时候节点之间的next已经是指向完成了，才会有 !=null，所以也不用替换next
                if (tailNext != null) {
                    //队列处于中间状态，推进尾节点
                    //B
                    return tail.compareAndSet(curTail, tailNext);
                } else {
                    //处于稳定状态,也就是正常替换的流程，把当前尾部空node指向 newNode
                    if (curTail.next.compareAndSet(null, newNode)) {
                        //插入操作成功，尝试推进尾节点 当前尾部节点指向 newNode
                        tail.compareAndSet(curTail, newNode);
                        //如果上一步失败，那么本次插入操作的线程将返回，而不是重新执行CAS，因为另一个线程B中完成了这个工作
                        return true;
                    }
                }
            }
        }
    }

}
